from RandomList import GetRandomList

def heapify(arr, n, i): 
    largest = i  
    l = 2 * i + 1     
    r = 2 * i + 2     
    if l < n and arr[i] < arr[l]: 
        largest = l 
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]  
        heapify(arr, n, largest) 
  
def max_heap_sort(arr): 
    n = len(arr) 
    # Build a maxheap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   
        # 一直把最大的放到最后并确保最顶上总是最大
        heapify(arr, i, 0) 
    return arr
  

if __name__ == "__main__":
    Arr = GetRandomList(7000)
    
    
